home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 090 / byte1087.arc / BPSIM.C next >
C/C++ Source or Header  |  1987-08-12  |  16KB  |  564 lines
  1. /*
  2.  * title:    bpsim.c
  3.  * author:    Josiah C. Hoskins
  4.  * date:    June 1987
  5.  *
  6.  * purpose:    backpropagation learning rule neural net simulator
  7.  *        for the tabula rasa Little Red Riding Hood example
  8.  *
  9.  * description: Bpsim provides an implementation of a neural network
  10.  *        containing a single hidden layer which uses the
  11.  *        generalized backpropagation delta rule for learning.
  12.  *        A simple user interface is supplied for experimenting
  13.  *        with a neural network solution to the Little Red Riding
  14.  *        Hood example described in the text.
  15.  *
  16.  *        In addition, bpsim contains some useful building blocks
  17.  *        for further experimentation with single layer neural
  18.  *        networks. The data structure which describes the general
  19.  *        processing unit allows one to easily investigate different
  20.  *        activation (output) and/or error functions. The utility
  21.  *        function create_link can be used to create links between
  22.  *        any two units by supplying your own create_in_out_links
  23.  *        function. The flexibility of creating units and links
  24.  *        to your specifications allows one to modify the code
  25.  *        to tune the network architecture to problems of interest.
  26.  *
  27.  *        There are some parameters that perhaps need some
  28.  *        explanation. You will notice that the target values are
  29.  *        either 0.1 or 0.9 (corresponding to the binary values
  30.  *        0 or 1). With the sigmoidal function used in out_f the
  31.  *        weights become very large if 0 and 1 are used as targets.
  32.  *        The ON_TOLERANCE value is used as a criteria for an output
  33.  *        value to be considered "on", i.e., close enough to the
  34.  *        target of 0.9 to be considered 1. The learning_rate and
  35.  *        momentum variables may be changed to vary the rate of
  36.  *        learning, however, in general they each should be less
  37.  *        than 1.0.
  38.  *
  39.  *        Bpsim has been compiled using CI-C86 version 2.30 on an
  40.  *        IBM-PC and the Sun C compiler on a Sun 3/160.
  41.  *
  42.  *        Note to compile and link on U*IX machines use:
  43.  *            cc -o bpsim bpsim.c -lm
  44.  *
  45.  *        For other machines remember to link in the math library.
  46.  *
  47.  * status:    This program may be freely used, modified, and distributed
  48.  *        except for commercial purposes.
  49.  *
  50.  * Copyright (c) 1987    Josiah C. Hoskins
  51.  */
  52.  
  53. #include <math.h>
  54. #include <stdio.h>
  55. #include <ctype.h>
  56.  
  57. #define BUFSIZ        512
  58.  
  59. #define FALSE        0
  60. #define TRUE        !FALSE
  61. #define NUM_IN        6    /* number of input units */
  62. #define NUM_HID     3    /* number of hidden units */
  63. #define NUM_OUT     7    /* number of output units */
  64. #define TOTAL        (NUM_IN + NUM_HID + NUM_OUT)
  65. #define BIAS_UID    (TOTAL) /* threshold unit */
  66.  
  67. /* macros to provide indexes for processing units */
  68. #define IN_UID(X)    (X)
  69. #define HID_UID(X)    (NUM_IN + X)
  70. #define OUT_UID(X)    (NUM_IN + NUM_HID + X)
  71. #define TARGET_INDEX(X) (X - (NUM_IN + NUM_HID))
  72.  
  73. #define WOLF_PATTERN    0
  74. #define GRANDMA_PATTERN 1
  75. #define WOODCUT_PATTERN 2
  76. #define PATTERNS    3    /* number of input patterns */
  77. #define ERROR_TOLERANCE 0.01
  78. #define ON_TOLERANCE    0.8    /* a unit's output is on if > ON_TOLERENCE */
  79. #define NOTIFY        10    /* iterations per dot notification */
  80. #define DEFAULT_ITER    250
  81.  
  82. struct unit {            /* general processing unit */
  83.   int     uid;            /* integer uniquely identifying each unit */
  84.   char     *label;
  85.   double output;        /* activation level */
  86.   double (*unit_out_f)();    /* note output fcn == activation fcn*/
  87.   double delta;         /* delta for unit */
  88.   double (*unit_delta_f)();    /* ptr to function to calc delta */
  89.   struct link *inlinks;     /* for propagation */
  90.   struct link *outlinks;    /* for back propagation */
  91. } *pu[TOTAL+1];         /* one extra for the bias unit */
  92.  
  93. struct link {            /* link between two processing units */
  94.   char     *label;
  95.   double weight;        /* connection or link weight */
  96.   double data;            /* used to hold the change in weights */
  97.   int     from_unit;        /* uid of from unit */
  98.   int     to_unit;        /* uid of to unit */
  99.   struct link *next_inlink;
  100.   struct link *next_outlink;
  101. };
  102.  
  103. int    iterations = DEFAULT_ITER;
  104. double    learning_rate = 0.2;
  105. double    momentum = 0.9;
  106. double    pattern_err[PATTERNS];
  107.  
  108. /*
  109.  * Input Patterns
  110.  * {Big Ears, Big Eyes, Big Teeth, Kindly, Wrinkled, Handsome}
  111.  *   unit 0    unit 1      unit 2   unit 3   unit 4    unit 5
  112.  */
  113. double    input_pat[PATTERNS+1][NUM_IN] = {
  114.   {1.0, 1.0, 1.0, 0.0, 0.0, 0.0},    /* Wolf */
  115.   {0.0, 1.0, 0.0, 1.0, 1.0, 0.0},    /* Grandma */
  116.   {1.0, 0.0, 0.0, 1.0, 0.0, 1.0},    /* Woodcutter */
  117.   {0.0, 0.0, 0.0, 0.0, 0.0, 0.0},    /* Used for Recognize Mode */
  118. };
  119.  
  120. /*
  121.  * Target Patterns
  122.  * {Scream, Run Away, Look for Woodcutter, Approach, Kiss on Cheek,
  123.  *    Offer Food, Flirt with}
  124.  */
  125. double    target_pat[PATTERNS][NUM_OUT] = {
  126.   {0.9, 0.9, 0.9, 0.1, 0.1, 0.1, 0.1},    /* response to Wolf */
  127.   {0.1, 0.1, 0.1, 0.9, 0.9, 0.9, 0.1},    /* response to Grandma */
  128.   {0.1, 0.1, 0.1, 0.9, 0.1, 0.9, 0.9},    /* response to Woodcutter */
  129. };
  130.  
  131. /*
  132.  * function declarations
  133.  */
  134. void    print_header();
  135. char    get_command();
  136. double    out_f(), delta_f_out(), delta_f_hid(), random(), pattern_error();
  137.  
  138.  
  139. main()
  140. {
  141.   char     ch;
  142.   extern struct unit *pu[];
  143.  
  144.   print_header();
  145.   create_processing_units(pu);
  146.   create_in_out_links(pu);
  147.   for (;;) {
  148.     ch = get_command("\nEnter Command (Learn, Recognize, Quit) => ");
  149.     switch (ch) {
  150.     case 'l':
  151.     case 'L':
  152.       printf("\n\tLEARN MODE\n\n");
  153.       learn(pu);
  154.       break;
  155.     case 'r':
  156.     case 'R':
  157.       printf("\n\tRECOGNIZE MODE\n\n");
  158.       recognize(pu);
  159.       break;
  160.     case 'q':
  161.     case 'Q':
  162.       exit(1);
  163.       break;
  164.     default:
  165.       fprintf(stderr, "Invalid Command\n");
  166.       break;
  167.     }
  168.   }
  169. }
  170.  
  171.  
  172. void
  173. print_header()
  174. {
  175.   printf("%s%s%s",
  176.      "\n\tBPSIM -- Back Propagation Learning Rule Neural Net Simulator\n",
  177.      "\t\t for the tabula rasa Little Red Riding Hood example.\n\n",
  178.      "\t\t Written by Josiah C. Hoskins\n");
  179. }
  180.  
  181.  
  182. /*
  183.  * create input, hidden, output units (and threshold or bias unit)
  184.  */
  185. create_processing_units(pu)
  186. struct    unit *pu[];
  187. {
  188.   int    id;            /* processing unit index */
  189.   struct unit *create_unit();
  190.  
  191.   for (id = IN_UID(0); id < IN_UID(NUM_IN); id++)
  192.     pu[id] = create_unit(id, "input", 0.0, NULL, 0.0, NULL);
  193.   for (id = HID_UID(0); id < HID_UID(NUM_HID); id++)
  194.     pu[id] = create_unit(id, "hidden", 0.0, out_f, 0.0, delta_f_hid);
  195.   for (id = OUT_UID(0); id < OUT_UID(NUM_OUT); id++)
  196.     pu[id] = create_unit(id, "output", 0.0, out_f, 0.0, delta_f_out);
  197.   pu[BIAS_UID] = create_unit(BIAS_UID, "bias", 1.0, NULL, 0.0, NULL);
  198. }
  199.  
  200.  
  201. /*
  202.  * create links - fully connected for each layer
  203.  *          note: the bias unit has one link to ea hid and out unit
  204.  */
  205. create_in_out_links(pu)
  206. struct    unit *pu[];
  207. {
  208.   int    i, j;        /* i == to and j == from unit id's */
  209.   struct link *create_link();
  210.  
  211.   /* fully connected units */
  212.   for (i = HID_UID(0); i < HID_UID(NUM_HID); i++) { /* links to hidden */
  213.     pu[BIAS_UID]->outlinks =
  214.       pu[i]->inlinks = create_link(pu[i]->inlinks, i,
  215.                    pu[BIAS_UID]->outlinks, BIAS_UID,
  216.                    (char *)NULL,
  217.                    random(), 0.0);
  218.     for (j = IN_UID(0); j < IN_UID(NUM_IN); j++) /* from input units */
  219.       pu[j]->outlinks =
  220.     pu[i]->inlinks = create_link(pu[i]->inlinks, i, pu[j]->outlinks, j,
  221.                      (char *)NULL, random(), 0.0);
  222.   }
  223.   for (i = OUT_UID(0); i < OUT_UID(NUM_OUT); i++) {    /* links to output */
  224.     pu[BIAS_UID]->outlinks =
  225.         pu[i]->inlinks = create_link(pu[i]->inlinks, i,
  226.                      pu[BIAS_UID]->outlinks, BIAS_UID,
  227.                      (char *)NULL, random(), 0.0);
  228.     for (j = HID_UID(0); j < HID_UID(NUM_HID); j++) /* from hidden units */
  229.       pu[j]->outlinks =
  230.     pu[i]->inlinks = create_link(pu[i]->inlinks, i, pu[j]->outlinks, j,
  231.                      (char *)NULL, random(), 0.0);
  232.   }
  233. }
  234.  
  235.  
  236. /*
  237.  * return a random number bet 0.0 and 1.0
  238.  */
  239. double
  240. random()
  241. {
  242.   return((rand() % 32727) / 32737.0);
  243. }
  244.  
  245.  
  246. /*
  247.  * the next two functions are general utility functions to create units
  248.  * and create links
  249.  */
  250. struct unit *
  251. create_unit(uid, label, output, out_f, delta, delta_f)
  252. int  uid;
  253. char *label;
  254. double     output, delta;
  255. double     (*out_f)(), (*delta_f)();
  256. {
  257.   struct unit  *unitptr;
  258.  
  259.   if (!(unitptr = (struct unit *)malloc(sizeof(struct unit)))) {
  260.     fprintf(stderr, "create_unit: not enough memory\n");
  261.     exit(1);
  262.   }
  263.   /* initialize unit data */
  264.   unitptr->uid = uid;
  265.   unitptr->label = label;
  266.   unitptr->output = output;
  267.   unitptr->unit_out_f = out_f;    /* ptr to output fcn */
  268.   unitptr->delta = delta;
  269.   unitptr->unit_delta_f = delta_f;
  270.   return (unitptr);
  271. }
  272.  
  273.  
  274. struct link *
  275. create_link(start_inlist, to_uid, start_outlist, from_uid, label, wt, data)
  276. struct    link *start_inlist, *start_outlist;
  277. int    to_uid, from_uid;
  278. char *    label;
  279. double    wt, data;
  280. {
  281.   struct link  *linkptr;
  282.  
  283.   if (!(linkptr = (struct link *)malloc(sizeof(struct link)))) {
  284.     fprintf(stderr, "create_link: not enough memory\n");
  285.     exit(1);
  286.   }
  287.   /* initialize link data */
  288.   linkptr->label = label;
  289.   linkptr->from_unit = from_uid;
  290.   linkptr->to_unit = to_uid;
  291.   linkptr->weight = wt;
  292.   linkptr->data = data;
  293.   linkptr->next_inlink = start_inlist;
  294.   linkptr->next_outlink = start_outlist;
  295.   return(linkptr);
  296. }
  297.  
  298.  
  299. char
  300. get_command(s)
  301. char    *s;
  302. {
  303.   char    command[BUFSIZ];
  304.  
  305.   fputs(s, stdout);
  306.   fflush(stdin); fflush(stdout);
  307.   (void)fgets(command, BUFSIZ, stdin);
  308.   return((command[0]));     /* return 1st letter of command */
  309. }
  310.  
  311.  
  312. learn(pu)
  313. struct unit *pu[];
  314. {
  315.   register i, temp;
  316.   char     tempstr[BUFSIZ];
  317.   extern int    iterations;
  318.   extern double learning_rate, momentum;
  319.   static char prompt[] = "Enter # iterations (default is 250) => ";
  320.   static char quote1[] = "Perhaps, Little Red Riding Hood ";
  321.   static char quote2[] = "should do more learning.\n";
  322.  
  323.   printf(prompt);
  324.   fflush(stdin); fflush(stdout);
  325.   gets(tempstr);
  326.   if (temp = atoi(tempstr))
  327.     iterations = temp;
  328.  
  329.   printf("\nLearning ");
  330.   for (i = 0; i < iterations; i++) {
  331.     if ((i % NOTIFY) == 0) {
  332.       printf(".");
  333.       fflush(stdout);
  334.     }
  335.     bp_learn(pu, (i == iterations-2 || i == iterations-1 || i == iterations));
  336.   }
  337.   printf(" Done\n\n");
  338.   printf("Error for Wolf pattern = \t%lf\n", pattern_err[0]);
  339.   printf("Error for Grandma pattern = \t%lf\n", pattern_err[1]);
  340.   printf("Error for Woodcutter pattern = \t%lf\n", pattern_err[2]);
  341.   if (pattern_err[WOLF_PATTERN] > ERROR_TOLERANCE) {
  342.     printf("\nI don't know the Wolf very well.\n%s%s", quote1, quote2);
  343.   } else if (pattern_err[GRANDMA_PATTERN] > ERROR_TOLERANCE) {
  344.     printf("\nI don't know Grandma very well.\n%s%s", quote1, quote2);
  345.   } else if (pattern_err[WOODCUT_PATTERN] > ERROR_TOLERANCE) {
  346.     printf("\nI don't know Mr. Woodcutter very well.\n%s%s", quote1, quote2);
  347.   } else {
  348.     printf("\nI feel pretty smart, now.\n");
  349.   }
  350. }
  351.  
  352.  
  353. /*
  354.  * back propagation learning
  355.  */
  356. bp_learn(pu, save_error)
  357. struct unit *pu[];
  358. int    save_error;
  359. {
  360.   static int count = 0;
  361.   static int pattern = 0;
  362.   extern double pattern_err[PATTERNS];
  363.  
  364.   init_input_units(pu, pattern); /* initialize input pattern to learn */
  365.   propagate(pu);         /* calc outputs to check versus targets */
  366.   if (save_error)
  367.     pattern_err[pattern] = pattern_error(pattern, pu);
  368.   bp_adjust_weights(pattern, pu);
  369.   if (pattern < PATTERNS - 1)
  370.     pattern++;
  371.   else
  372.       pattern = 0;
  373.   count++;
  374. }
  375.  
  376.  
  377. /*
  378.  * initialize the input units with a specific input pattern to learn
  379.  */
  380. init_input_units(pu, pattern)
  381. struct unit *pu[];
  382. int    pattern;
  383. {
  384.   int    id;
  385.  
  386.   for (id = IN_UID(0); id < IN_UID(NUM_IN); id++)
  387.     pu[id]->output = input_pat[pattern][id];
  388. }
  389.  
  390.  
  391. /*
  392.  * calculate the activation level of each unit
  393.  */
  394. propagate(pu)
  395. struct unit *pu[];
  396. {
  397.   int    id;
  398.  
  399.   for (id = HID_UID(0); id < HID_UID(NUM_HID); id++)
  400.     (*(pu[id]->unit_out_f))(pu[id], pu);
  401.   for (id = OUT_UID(0); id < OUT_UID(NUM_OUT); id++)
  402.     (*(pu[id]->unit_out_f))(pu[id], pu);
  403. }
  404.  
  405.  
  406. /*
  407.  * function to calculate the activation or output of units
  408.  */
  409. double
  410. out_f(pu_ptr, pu)
  411. struct unit *pu_ptr, *pu[];
  412. {
  413.   double sum = 0.0, exp();
  414.   struct link *tmp_ptr;
  415.  
  416.   tmp_ptr = pu_ptr->inlinks;
  417.   while (tmp_ptr) {
  418.     /* sum up (outputs from inlinks times weights on the inlinks) */
  419.     sum += pu[tmp_ptr->from_unit]->output * tmp_ptr->weight;
  420.     tmp_ptr = tmp_ptr->next_inlink;
  421.   }
  422.   pu_ptr->output = 1.0/(1.0 + exp(-sum));
  423. }
  424.  
  425.  
  426. /*
  427.  * half of the sum of the squares of the errors of the
  428.  * output versus target values
  429.  */
  430. double
  431. pattern_error(pat_num, pu)
  432. int    pat_num;    /* pattern number */
  433. struct    unit *pu[];
  434. {
  435.   int        i;
  436.   double    temp, sum = 0.0;
  437.  
  438.   for (i = OUT_UID(0); i < OUT_UID(NUM_OUT); i++) {
  439.     temp = target_pat[pat_num][TARGET_INDEX(i)] - pu[i]->output;
  440.     sum += temp * temp;
  441.   }
  442.   return (sum/2.0);
  443. }
  444.  
  445.  
  446. bp_adjust_weights(pat_num, pu)
  447. int    pat_num;    /* pattern number */
  448. struct    unit *pu[];
  449. {
  450.   int        i;        /* processing units id */
  451.   double    temp1, temp2, delta, error_sum;
  452.   struct link    *inlink_ptr, *outlink_ptr;
  453.  
  454.   /* calc deltas */
  455.   for (i = OUT_UID(0); i < OUT_UID(NUM_OUT); i++) /* for each output unit */
  456.     (*(pu[i]->unit_delta_f))(pu, i, pat_num); /* calc delta */
  457.   for (i = HID_UID(0); i < HID_UID(NUM_HID); i++) /* for each hidden unit */
  458.     (*(pu[i]->unit_delta_f))(pu, i);      /* calc delta */
  459.   /* calculate weights */
  460.   for (i = OUT_UID(0); i < OUT_UID(NUM_OUT); i++) {    /* for output units */
  461.     inlink_ptr = pu[i]->inlinks;
  462.     while (inlink_ptr) {    /* for each inlink to output unit */
  463.       temp1 = learning_rate * pu[i]->delta *
  464.     pu[inlink_ptr->from_unit]->output;
  465.       temp2 = momentum * inlink_ptr->data;
  466.       inlink_ptr->data = temp1 + temp2; /* new delta weight */
  467.       inlink_ptr->weight += inlink_ptr->data;    /* new weight */
  468.       inlink_ptr = inlink_ptr->next_inlink;
  469.     }
  470.   }
  471.   for (i = HID_UID(0); i < HID_UID(NUM_HID); i++) { /* for ea hid unit */
  472.     inlink_ptr = pu[i]->inlinks;
  473.     while (inlink_ptr) {    /* for each inlink to output unit */
  474.       temp1 = learning_rate * pu[i]->delta *
  475.     pu[inlink_ptr->from_unit]->output;
  476.       temp2 = momentum * inlink_ptr->data;
  477.       inlink_ptr->data = temp1 + temp2; /* new delta weight */
  478.       inlink_ptr->weight += inlink_ptr->data;    /* new weight */
  479.     inlink_ptr = inlink_ptr->next_inlink;
  480.     }
  481.   }
  482. }
  483.  
  484.  
  485. /*
  486.  * calculate the delta for an output unit
  487.  */
  488. double
  489. delta_f_out(pu, uid, pat_num)
  490. struct unit *pu[];
  491. int    uid, pat_num;
  492. {
  493.   double    temp1, temp2, delta;
  494.  
  495.   /* calc deltas */
  496.   temp1 = (target_pat[pat_num][TARGET_INDEX(uid)] - pu[uid]->output);
  497.   temp2 = (1.0 - pu[uid]->output);
  498.   delta = temp1 * pu[uid]->output * temp2; /* calc delta */
  499.   pu[uid]->delta = delta; /* store delta to pass on */
  500. }
  501.  
  502.  
  503. /*
  504.  * calculate the delta for a hidden unit
  505.  */
  506. double
  507. delta_f_hid(pu, uid)
  508. struct unit *pu[];
  509. int    uid;
  510. {
  511.   double    temp1, temp2, delta, error_sum;
  512.   struct link    *inlink_ptr, *outlink_ptr;
  513.  
  514.   outlink_ptr = pu[uid]->outlinks;
  515.   error_sum = 0.0;
  516.   while (outlink_ptr) {
  517.     error_sum += pu[outlink_ptr->to_unit]->delta * outlink_ptr->weight;
  518.     outlink_ptr = outlink_ptr->next_outlink;
  519.   }
  520.   delta = pu[uid]->output * (1.0 - pu[uid]->output) * error_sum;
  521.   pu[uid]->delta = delta;
  522. }
  523.  
  524.  
  525. recognize(pu)
  526. struct unit *pu[];
  527. {
  528.   int     i;
  529.   char     tempstr[BUFSIZ];
  530.   static char *p[] = {"Big Ears?", "Big Eyes?", "Big Teeth?",
  531.               "Kindly?\t", "Wrinkled?", "Handsome?"};
  532.  
  533.   for (i = 0; i < NUM_IN; i++) {
  534.     printf("%s\t(y/n) ", p[i]);
  535.     fflush(stdin); fflush(stdout);
  536.     fgets(tempstr, BUFSIZ, stdin);
  537.     if (tempstr[0] == 'Y' || tempstr[0] == 'y')
  538.       input_pat[PATTERNS][i] = 1.0;
  539.     else
  540.       input_pat[PATTERNS][i] = 0.0;
  541.   }
  542.   init_input_units(pu, PATTERNS);
  543.   propagate(pu);
  544.   print_behaviour(pu);
  545. }
  546.  
  547.  
  548. print_behaviour(pu)
  549. struct unit *pu[];
  550. {
  551.   int    id, count = 0;
  552.   static char *behaviour[] = {
  553.     "Screams", "Runs Away", "Looks for Woodcutter", "Approaches",
  554.     "Kisses on Cheek", "Offers Food", "Flirts with Woodcutter" };
  555.  
  556.   printf("\nLittle Red Riding Hood: \n");
  557.   for (id = OUT_UID(0); id < OUT_UID(NUM_OUT); id++){ /* links to out units */
  558.     if (pu[id]->output > ON_TOLERANCE)
  559.       printf("\t%s\n", behaviour[count]);
  560.     count++;
  561.   }
  562.   printf("\n");
  563. }
  564.